Subject: Re: Can't you make your mailer attach appropriate subject, Ariel?

From: [email-masked] (Ariel Orda)
Date: Thu, 15 May 1997 17:55:31 +0300

Masataka,

As I already said, I feel that the discussion is going nowhere, thus I 
have no interest in pursuing it further.

Nevertheless, I am happy to see that you finally understood my algorithm 
and that you now agree that the claims that I have made about it are 
correct, in particular wrt the complexity:

  >Yes, if you modify BF to record pathes found at each outer iteration
  >of BF, you don't have to iterate the entire BF to find the best path
  >and the complexity remains same.
  >
  >But, it is not what you described.
  >
  >
It *is* what I described. I repeat below, verbatim, the algorithm that I
specified (my message of May 5). In particular, please look at step (2).

------------------------------------------------------------------------
(1) Execute the Bellman-Ford algorithm for all (up to M) bandwidth/rate 
values.

(2) In each execution, record the shortest path (w.r.t. the "constant 
delays" metric of each link) for each possible hop count.

This results in a total of O(M*H) paths, where H=<the network
diameter. 

(3) Check then the best end-to-end bound for each path, and discard
those that do not meet the delay constraint. Note that in the case
of the GS model, this means computing the end-to-end delay bound
on each path assuming the (maximum) bandwidth value B_m used in the
execution of the Bellman-Ford algorithm during which the path was
computed.

(4) For each remaining path, choose the minimum possible bandwidth to 
be consumed (on all links of the path) such that the delay constraint 
remains satisfied (note that the consumed bandwidth is no more, and 
typically less, than B_m).

(5) Now choose the path with the minimal bandwidth. 
------------------------------------------------------------------------

Ariel